{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Zero-Filled Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: zeroFilledSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #全 0 子数组的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;，返回全部为&nbsp;<code>0</code>&nbsp;的&nbsp;<strong>子数组</strong>&nbsp;数目。</p>\n",
    "\n",
    "<p><strong>子数组</strong>&nbsp;是一个数组中一段连续非空元素组成的序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,3,0,0,2,0,0,4]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>\n",
    "子数组 [0] 出现了 4 次。\n",
    "子数组 [0,0] 出现了 2 次。\n",
    "不存在长度大于 2 的全 0 子数组，所以我们返回 6 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [0,0,0,2,0,0]\n",
    "<b>输出：</b>9\n",
    "<strong>解释：\n",
    "</strong>子数组 [0] 出现了 5 次。\n",
    "子数组 [0,0] 出现了 3 次。\n",
    "子数组 [0,0,0] 出现了 1 次。\n",
    "不存在长度大于 3 的全 0 子数组，所以我们返回 9 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,10,2019]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>没有全 0 子数组，所以我们返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-zero-filled-subarrays](https://leetcode.cn/problems/number-of-zero-filled-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-zero-filled-subarrays](https://leetcode.cn/problems/number-of-zero-filled-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,0,0,2,0,0,4]', '[0,0,0,2,0,0]', '[2,10,2019]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt_zero = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                cnt_zero += 1\n",
    "            else:\n",
    "                if cnt_zero:\n",
    "                    ans += (1 + cnt_zero) * cnt_zero // 2\n",
    "                cnt_zero = 0\n",
    "        ans += (1+cnt_zero) * cnt_zero // 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = cnt = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += cnt * (cnt + 1) // 2\n",
    "                cnt = 0\n",
    "        ans += cnt * (cnt + 1) // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x != 0:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        \n",
    "        i = 0\n",
    "        ans = 0\n",
    "\n",
    "        while i < len(nums):\n",
    "            while i < len(nums) and nums[i] != 0:\n",
    "                i += 1\n",
    "            \n",
    "            if i == len(nums):\n",
    "                break\n",
    "\n",
    "            start = i \n",
    "\n",
    "            while i < len(nums) and nums[i] == 0:\n",
    "                i += 1\n",
    "            \n",
    "            size = i - 1 - start + 1\n",
    "\n",
    "            ans += (1 + size) * size // 2\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        cnt = ret = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ret += cnt * (cnt + 1) // 2\n",
    "                cnt = 0\n",
    "        return ret + cnt * (cnt + 1) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        # i = 0\n",
    "        # n = len(nums)\n",
    "        # ans = 0\n",
    "        # while i<n:\n",
    "        #     if nums[i]==0:\n",
    "        #         cur = i\n",
    "        #         while cur<n and nums[cur] == 0:\n",
    "        #             cur+=1\n",
    "                \n",
    "        #         ans += ((cur-i)*(cur-i+1))//2\n",
    "        #         i =cur\n",
    "        #     else:\n",
    "        #         i+=1\n",
    "        \n",
    "        # return ans\n",
    "\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for num in nums:\n",
    "            if num:\n",
    "                cur = 0\n",
    "            else:\n",
    "                cur+=1\n",
    "                ans +=cur\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        nums.append(1)\n",
    "        set01 = {}\n",
    "        daan = 0\n",
    "        num = 0\n",
    "        for x in range(len(nums)):\n",
    "            if nums[x] == 0:\n",
    "                num += 1\n",
    "            else:\n",
    "                if num in set01:\n",
    "                    set01[num] += 1\n",
    "                else:\n",
    "                    set01[num] = 1\n",
    "                num = 0\n",
    "        for x in set01:\n",
    "            daan += x * (x+1) // 2 * set01[x]\n",
    "        return daan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for n, grp in groupby(nums):\n",
    "            if not n:\n",
    "                n = sum(1 for _ in grp)\n",
    "                result += (n + 1)*n //2\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(n):\n",
    "    sum1 = 0\n",
    "    for i in range(1,n+1):\n",
    "        sum1+=i\n",
    "    return sum1    \n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums) -> int:\n",
    "        count = 0\n",
    "        i,j=0,0\n",
    "        while i<len(nums):\n",
    "            while i<len(nums) and nums[i] != 0:\n",
    "                i+=1\n",
    "            j=i\n",
    "            while j<len(nums) and nums[j] == 0 :\n",
    "                j+=1\n",
    "            count +=func1(j-i)\n",
    "\n",
    "            i=j\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        set01 = {}\n",
    "        daan = 0\n",
    "        num = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                num += 1\n",
    "            else:\n",
    "                if num != 0:\n",
    "                    if num in set01:\n",
    "                        set01[num] += 1\n",
    "                    else:\n",
    "                        set01[num] = 1\n",
    "                num = 0\n",
    "        if num != 0:\n",
    "            if num in set01:\n",
    "                set01[num] += 1\n",
    "            else:\n",
    "                set01[num] = 1\n",
    "        for x in set01:\n",
    "            daan += x * (x+1) // 2 * set01[x]\n",
    "        return daan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        set01 = {}\n",
    "        daan = 0\n",
    "        num = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                num += 1\n",
    "            elif num != 0:\n",
    "                if num in set01:\n",
    "                    set01[num] += 1\n",
    "                else:\n",
    "                    set01[num] = 1\n",
    "                num = 0\n",
    "        if num != 0:\n",
    "            if num in set01:\n",
    "                set01[num] += 1\n",
    "            else:\n",
    "                set01[num] = 1\n",
    "        for x in set01:\n",
    "            daan += x * (x+1) // 2 * set01[x]\n",
    "        return daan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "#         dic = set()\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num == 0:\n",
    "#                 dic.add(i)\n",
    "#         res = 0\n",
    "#         for i in list(dic):\n",
    "#             if i-1 in dic:\n",
    "#                 continue\n",
    "#             count = 1\n",
    "#             cur = i\n",
    "#             while cur + 1 in dic:\n",
    "#                 count +=1\n",
    "#                 cur += 1\n",
    "#             for j in range(1, count+ 1): # j is length\n",
    "#                 res += count -j + 1\n",
    "#         return res\n",
    "         \n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if nums[i] != 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                count = 1\n",
    "                cur = i\n",
    "                while cur + 1 < n and nums[cur+1] == 0: # cur + 1 not cur\n",
    "                    count += 1\n",
    "                    cur  += 1\n",
    "                for j in range(1, count + 1):\n",
    "                    res += count -j + 1\n",
    "                i = cur +1 # i = cur + 1!!!!\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += (1 + cnt) * cnt // 2\n",
    "                cnt = 0\n",
    "        \n",
    "        ans += (1 + cnt) * cnt // 2\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans=[]\n",
    "        count=0\n",
    "        for i in nums:\n",
    "            if i ==0:\n",
    "                count+=1\n",
    "                ans.append(count)\n",
    "            else:\n",
    "                count =0\n",
    "        return sum(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        for n in nums:\n",
    "            if n == 0:\n",
    "                count += 1\n",
    "            elif count > 0:\n",
    "                ans += count * (count + 1) >> 1\n",
    "                count = 0\n",
    "        ans += count * (count + 1) >> 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        nums.append(1)\n",
    "        set01 = {}\n",
    "        daan = 0\n",
    "        num = 0\n",
    "        for x in range(len(nums)):\n",
    "            if nums[x] == 0:\n",
    "                num += 1\n",
    "            elif num != 0:\n",
    "                if num in set01:\n",
    "                    set01[num] += 1\n",
    "                else:\n",
    "                    set01[num] = 1\n",
    "                num = 0\n",
    "        for x in set01:\n",
    "            daan += x * (x+1) // 2 * set01[x]\n",
    "        return daan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        i, res = 0, 0\n",
    "        while i < len(nums):\n",
    "            count = 0\n",
    "            while i < len(nums) and nums[i] == 0:\n",
    "                count += 1\n",
    "                i += 1\n",
    "                res += count\n",
    "            i += 1\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if nums[i] == 0:\n",
    "                j = i + 1\n",
    "                while j < n and nums[j] == 0:\n",
    "                    j += 1\n",
    "                m = j - i \n",
    "                ans += m * (m + 1) // 2\n",
    "                i = j\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                cnt += 1\n",
    "                ans += cnt\n",
    "            else:\n",
    "                cnt = 0\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        num=0\n",
    "        real=0\n",
    "        numms=0\n",
    "        k=0\n",
    "        for i in nums:\n",
    "            k=k+1\n",
    "            if i==0:\n",
    "                num+=1\n",
    "                if k==len(nums):\n",
    "                    real = num\n",
    "                    num = 0\n",
    "                    numms = numms + (1+real)*real/2\n",
    "            else:\n",
    "                real=num\n",
    "                num=0\n",
    "                numms=numms+(1+real)*real/2\n",
    "        return int(numms)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while i<n:\n",
    "            if nums[i]==0:\n",
    "                cur = i\n",
    "                while cur<n and nums[cur] == 0:\n",
    "                    cur+=1\n",
    "                \n",
    "                ans += ((cur-i)*(cur-i+1))//2\n",
    "                i =cur\n",
    "            else:\n",
    "                i+=1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        set01 = {}\n",
    "        daan = 0\n",
    "        num = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                num += 1\n",
    "            elif num != 0:\n",
    "                key_num = num * (num + 1) // 2\n",
    "                if key_num in set01:\n",
    "                    set01[key_num] += 1\n",
    "                else:\n",
    "                    set01[key_num] = 1\n",
    "                num = 0\n",
    "        if num != 0:\n",
    "            key_num = num * (num + 1) // 2\n",
    "            if key_num in set01:\n",
    "                set01[key_num] += 1\n",
    "            else:\n",
    "                set01[key_num] = 1\n",
    "        for x in set01:\n",
    "            daan += x * set01[x]\n",
    "        return daan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        nums.append(\"*\")\n",
    "        set01 = {}\n",
    "        daan = 0\n",
    "        num = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                num += 1\n",
    "            elif num != 0:\n",
    "                if num in set01:\n",
    "                    set01[num] += 1\n",
    "                else:\n",
    "                    set01[num] = 1\n",
    "                num = 0\n",
    "        for x in set01:\n",
    "            daan += x * (x+1) // 2 * set01[x]\n",
    "        return daan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums=[1]+nums+[1]\n",
    "        res=0\n",
    "        q=1\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            if nums[i+1]==nums[i]==0:\n",
    "                res+=q\n",
    "                q+=1\n",
    "                \n",
    "            if nums[i]==0 and nums[i+1]!=0 :\n",
    "                res+=q\n",
    "                q=1\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "#         dic = set()\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num == 0:\n",
    "#                 dic.add(i)\n",
    "#         res = 0\n",
    "#         for i in list(dic):\n",
    "#             if i-1 in dic:\n",
    "#                 continue\n",
    "#             count = 1\n",
    "#             cur = i\n",
    "#             while cur + 1 in dic:\n",
    "#                 count +=1\n",
    "#                 cur += 1\n",
    "#             for j in range(1, count+ 1): # j is length\n",
    "#                 res += count -j + 1\n",
    "#         return res\n",
    "         \n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if nums[i] != 0:\n",
    "                i += 1\n",
    "            else:\n",
    "                count = 1\n",
    "                cur = i\n",
    "                while cur + 1 < n and nums[cur+1] == 0: # cur + 1 not cur\n",
    "                    count += 1\n",
    "                    cur  += 1\n",
    "                for j in range(1, count + 1):\n",
    "                    res += count -j + 1\n",
    "                if count == 1:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    i = cur +1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "1, 0, 0, 0, 1\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        res = 0\n",
    "        nums = [1] + nums\n",
    "        n = len(nums)\n",
    "        for right in range(n):\n",
    "            if nums[right] != 0:\n",
    "                res += ((right - left - 1) + 1) * (right - left - 1) // 2\n",
    "                left = right\n",
    "        res += ((right - left) + 1) * (right - left) // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        nums.append(\"*\")\n",
    "        set01 = {}\n",
    "        daan = 0\n",
    "        num = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                num += 1\n",
    "            elif num != 0:\n",
    "                if num in set01:\n",
    "                    set01[num] += 1\n",
    "                else:\n",
    "                    set01[num] = 1\n",
    "                num = 0\n",
    "        if num != 0:\n",
    "            if num in set01:\n",
    "                set01[num] += 1\n",
    "            else:\n",
    "                set01[num] = 1\n",
    "        for x in set01:\n",
    "            daan += x * (x+1) // 2 * set01[x]\n",
    "        return daan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        cur = 1\n",
    "        for i in nums:\n",
    "            if i:\n",
    "                cur = 1\n",
    "            else:\n",
    "                res += cur\n",
    "                cur += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        continue0Start = -1\n",
    "        subarray_num = 0\n",
    "        ended = True\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                if ended:\n",
    "                    continue0Start = i\n",
    "                    ended = False\n",
    "            else:\n",
    "                if not ended:\n",
    "                    length_0 = i - continue0Start\n",
    "                    ended = True\n",
    "                    subarray_num += (1 + length_0) * length_0 // 2\n",
    "        \n",
    "        if not ended:\n",
    "            length_0 = len(nums) - continue0Start\n",
    "            subarray_num += (1 + length_0) * length_0 // 2\n",
    "        \n",
    "        return subarray_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        zero_cnt = 0\n",
    "        rtn = 0\n",
    "        for n in nums:\n",
    "            if n:\n",
    "                rtn += zero_cnt * (zero_cnt + 1) // 2\n",
    "                zero_cnt = 0\n",
    "            else:\n",
    "                zero_cnt += 1\n",
    "        rtn += zero_cnt * (zero_cnt + 1) // 2\n",
    "        return rtn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        fh = 0\n",
    "        x = 0\n",
    "        for i in nums:\n",
    "            if i:\n",
    "                if x:\n",
    "                    fh += (1+x)*x//2\n",
    "                    x = 0\n",
    "            else:\n",
    "                x += 1\n",
    "        return fh + ((1+x)*x//2 if x else 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if(num == 0):\n",
    "                cnt += 1\n",
    "            else:\n",
    "                result += cnt*(cnt+1)//2\n",
    "                cnt = 0\n",
    "        result += cnt*(cnt+1)//2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        li01 = []\n",
    "        daan = 0\n",
    "        num = 0\n",
    "        for x in nums:\n",
    "            if x == 0:\n",
    "                num += 1\n",
    "            else:\n",
    "                if num != 0:\n",
    "                    li01.append(num)\n",
    "                num = 0\n",
    "        if num != 0:\n",
    "            li01.append(num)\n",
    "        for x in li01:\n",
    "            daan += x*(x+1)//2\n",
    "        return daan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        i = 0\n",
    "        t = None\n",
    "        res = 0\n",
    "        while i < len(nums):\n",
    "            while i < len(nums) and nums[i] != 0:\n",
    "                i += 1\n",
    "            t = i \n",
    "            while i < len(nums) and nums[i] == 0:\n",
    "                i += 1\n",
    "            res = res + (i - t + 1) / 2 * (i - t)\n",
    "        \n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        for n in nums:\n",
    "            if n == 0:\n",
    "                cur += 1\n",
    "            else:\n",
    "                res += (cur * (cur + 1) // 2)\n",
    "                cur = 0\n",
    "        if cur:\n",
    "            res += (cur * (cur + 1) // 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        ind = 0\r\n",
    "        while(ind < len(nums)):\r\n",
    "            tmp = 0 \r\n",
    "            if nums[ind] == 0:\r\n",
    "                while(ind < len(nums) and nums[ind] == 0):\r\n",
    "                    tmp += 1\r\n",
    "                    ind += 1\r\n",
    "                res += tmp * (tmp + 1) // 2\r\n",
    "            else:\r\n",
    "                ind += 1\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        cnt = 0\n",
    "        for num in nums:\n",
    "            if(num == 0):\n",
    "                cnt += 1\n",
    "            else:\n",
    "                result += cnt*(cnt+1)//2\n",
    "                cnt = 0\n",
    "        result += cnt*(cnt+1)//2\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        ind = 0\r\n",
    "        while(ind < len(nums)):\r\n",
    "            tmp = 0 \r\n",
    "            if nums[ind] == 0:\r\n",
    "                while(ind < len(nums) and nums[ind] == 0):\r\n",
    "                    tmp += 1\r\n",
    "                    ind += 1\r\n",
    "            else:\r\n",
    "                ind += 1\r\n",
    "            res += tmp * (tmp + 1) // 2\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\n",
    "        ans = c = 0\n",
    "        for x in nums:\n",
    "            if x:\n",
    "                c = 0\n",
    "            else:\n",
    "                c += 1\n",
    "                ans += c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def zeroFilledSubarray(self, nums: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        ind = 0\r\n",
    "        while(ind < len(nums)):\r\n",
    "            tmp = 0 \r\n",
    "            if nums[ind] == 0:\r\n",
    "                while(ind < len(nums) and nums[ind] == 0):\r\n",
    "                    tmp += 1\r\n",
    "                    ind += 1\r\n",
    "                res += tmp * (tmp + 1) // 2\r\n",
    "            else:\r\n",
    "                ind += 1\r\n",
    "        return(res)\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
